// Copyright 2010 Keir Mierle. All rights reserved.

#include <cstdio>
#include <vector>
#include <iostream>
#include <cassert>


#include "using.h"
#include "inttypes.h"

// 2 x 64
const uint64 zorbist[128] = {
  0x96F7C571931F54F9ULL,
  0xFE2D55E5E019F704ULL,
  0x97F6F7F11B982CA3ULL,
  0x53EFA7ED59B849A2ULL,
  0xA409173F2E0BCB35ULL,
  0x8665B09801459AA5ULL,
  0xC0958FA04B7131C5ULL,
  0x9C8D371F5B33A341ULL,
  0x3028F5FD338FC670ULL,
  0x4D0104BE4F4E6B26ULL,
  0x03E99CCD47CC6229ULL,
  0x2542C9DD5136BA39ULL,
  0xB16FCE5B04CF13E3ULL,
  0x73868EB186A3E21FULL,
  0x8CBB8686DEB5ECBAULL,
  0xE8C175E1A5B3B3A2ULL,
  0x8D144DB37357C6E4ULL,
  0x63434AA195001C68ULL,
  0x1A03436053A36FA5ULL,
  0x0C363EB2A63F603DULL,
  0x7B67A717ABCF2913ULL,
  0xD289DE2C1E936C28ULL,
  0xFB524417008CD84EULL,
  0xFDA9834BA4B34D51ULL,
  0xB1B70DE1F28A65C7ULL,
  0x34847AC420640E2FULL,
  0x702C966111544AF8ULL,
  0x7F14CA59172DFD89ULL,
  0xB774F774D7B58C3AULL,
  0xC0A5BBBDE248B2F6ULL,
  0xB1B85769A0604A31ULL,
  0x21B90C48F9E82637ULL,
  0x38C792E1E166378EULL,
  0x489DE0B9522A638DULL,
  0xD7B8CAB2F8FB234BULL,
  0x4D83FB23962DF5F1ULL,
  0xD58D155AD35F0081ULL,
  0x33EE7CC2DE2F55A3ULL,
  0xA17DCC2DB3C75EB8ULL,
  0xAE9ADD1BF2DB1861ULL,
  0xEBFAA6B3511387D4ULL,
  0x8751CB1A670F1ADBULL,
  0xE7AE9712FD9D4C4CULL,
  0x59262FEBF2BFB0D8ULL,
  0x59E262EBCF7418E8ULL,
  0x7BF725650C35D8AAULL,
  0x2BBB896CE5EB89CAULL,
  0xDC704896E6D809E7ULL,
  0x323B8C472AD8C9A3ULL,
  0xEDE2FB2494174E63ULL,
  0xC3C83E6572C75A85ULL,
  0xF0E40938A979BC24ULL,
  0x5669F81349A32D5DULL,
  0x4A5EC54FE2C73958ULL,
  0x83A909D968E28967ULL,
  0x157E6D6849204403ULL,
  0x817B91BFBE7CBA72ULL,
  0x17BF8301F1191EC1ULL,
  0xA37F0E125B434F70ULL,
  0xD656F29509002AB3ULL,
  0xDE97E2DC724BEB46ULL,
  0x07939755492D85B6ULL,
  0xF2E39E1944061B90ULL,
  0xFF8B3961765E975AULL,
  0x075E6AA3AE065E54ULL,
  0xA7B102CC2AA68605ULL,
  0xCB605D3140A022BAULL,
  0x9A06F23D6AD06C6EULL,
  0x8746FDE0F0BA7FF7ULL,
  0x8271917D852F23AFULL,
  0xCE8E1A3C9C4B4894ULL,
  0x50457DCC9B96C24BULL,
  0x6E42ED37E4DDF096ULL,
  0x4735CA91B4D67156ULL,
  0x0753CADE02ECFB95ULL,
  0xCC649FA89B6BAC02ULL,
  0xF7BBF650C3C409CDULL,
  0xC59A51C55A6F736CULL,
  0x9521BDD93D63A84CULL,
  0x45B332BC5959F89FULL,
  0x1BB31AA01104042FULL,
  0x1CD9FD434583C0EDULL,
  0xE3300BF95E092EEFULL,
  0xA9DFED352370D796ULL,
  0xDF6514575B85BBA0ULL,
  0x8E7BA75477101AF3ULL,
  0x932EDD8D5AC3A767ULL,
  0xA21CC85A5EAB9B39ULL,
  0x68C68CC489BBF152ULL,
  0x8F53CB67D2B467A5ULL,
  0x331EC6C992D1EC4AULL,
  0xA544A1A6710CD726ULL,
  0xDEA6FA8F94F418C1ULL,
  0x1929A9EB5B9C45B3ULL,
  0xFA9B128ED43028EEULL,
  0x75928CDDAEE8EADBULL,
  0xCD89F4D3B2012D59ULL,
  0x6BCF6DDEBE501A5EULL,
  0x7E57915ED06C9F95ULL,
  0xDE3A789FE24CC7DDULL,
  0x0B03737F53D3CA8DULL,
  0x0D337EB83BFADE7CULL,
  0x030B6C8ECCDE9F57ULL,
  0x7E405945DEDDF8FBULL,
  0xD14B59AFAD016EBCULL,
  0x41D4C4458FCEC924ULL,
  0x567F7CE0E5B8AABFULL,
  0x5DB870A473F4DAE6ULL,
  0x3169D63FDFEB273DULL,
  0x783CAE0004268EBDULL,
  0x77E2AEC6AEF28754ULL,
  0xA0864F6C764BA635ULL,
  0x8392BF30E51148EFULL,
  0xD27EFDAA865B0DA1ULL,
  0x74BB3A15A5585822ULL,
  0x178C0D6130ACE8FAULL,
  0xE7ACC4C70A268906ULL,
  0xFB84575F12EBAA87ULL,
  0x2A6C183D847F8EA2ULL,
  0x8E41A4152C1E6CA2ULL,
  0x6DF4E9CA15B4DF8CULL,
  0x0154EC8EB49E9B02ULL,
  0x9216019966B3436EULL,
  0x064725A40DB4275FULL,
  0x590AAF9614F10635ULL,
  0xC45514B112E66AE7ULL,
  0xA2D719B03EAA0CFAULL,
  0xE13BDDD0B1823258ULL,
};

uint64 BitForPosition(int i, int j) {
  return 1ULL << (8ULL * i + j);
}

uint64 LowestBitPosition(uint64 bit) {
  uint64 position = 0ULL;
  while (bit >>= 1ULL) {
    position++;
  }
  return position;
}

void PositionForBit(uint64 bit, int *i, int *j) {
  uint64 position = LowestBitPosition(bit);
  *i = position / 8;
  *j = position % 8;
}

bool PieceAtPosition(uint64 pieces, int i, int j) {
  assert(i < 8);
  assert(j < 8);
  return pieces & BitForPosition(i, j);
}

bool Wins(uint64 pieces) {
  for (int i = 0; i < 8; ++i) {
    int in_a_row = 0;
    int in_a_col = 0;
    for (int j = 0; j < 8; ++j) {
      if (PieceAtPosition(pieces, i, j)) {
        in_a_row++;
        if (in_a_row == 5) {
          return true;
        }
      } else {
        in_a_row = 0;
      }
      if (PieceAtPosition(pieces, j, i)) {
        in_a_col++;
        if (in_a_col == 5) {
          return true;
        }
      } else {
        in_a_col = 0;
      }
    }
  }
  const int start_rows[] = { 0, 0, 0, 0, 1, 2, 3 };
  const int start_cols[] = { 0, 1, 2, 3, 0, 0, 0 };
  for (int k = 0; k < 7; ++k) {
    int si = start_rows[k];
    int sj = start_cols[k];
    int in_a_left_diagonal = 0;
    int in_a_right_diagonal = 0;
    for (int l = 0; l < 8 - max(si, sj); ++l) {
      // Left diagonal.
      if (PieceAtPosition(pieces, si + l, sj + l)) {
        in_a_left_diagonal++;
        if (in_a_left_diagonal == 5) {
          return true;
        }
      } else {
        in_a_left_diagonal = 0;
      }
      // Right diagonal.
      if (PieceAtPosition(pieces, si + l, 7 - sj - l)) {
        in_a_right_diagonal++;
        if (in_a_right_diagonal == 5) {
          return true;
        }
      } else {
        in_a_right_diagonal = 0;
      }
    }
  }
  return false;
}

// Fixed size: 8x8 
struct GomokuBoard {
  typedef uint64 Move;  // 1 at spot to play.

  GomokuBoard() : black(0), white(0), hash(0), white_to_play(false) {}
  GomokuBoard(const GomokuBoard &other)
    : black(other.black),
      white(other.white),
      hash(other.hash),
      white_to_play(other.white_to_play) {}

  uint64 Hash() const { return hash; }

  int AvailableMoves() const {
    uint64 empty_spaces = ~(black | white);
    int count = 0;
    while (empty_spaces) {
       count += empty_spaces & 1;
       empty_spaces >>= 1;
    }
    return count;
  }

  void GenerateMoves(vector<Move> *moves) const {
    uint64 empty_spaces = ~(black | white);
    for (int i = 0; i < 8; ++i) {
      for (int j = 0; j < 8; ++j) {
        if (empty_spaces & BitForPosition(i, j)) {
          moves->push_back(8 * i + j);
        }
      }
    }
  }

  bool IsTerminal() const {
    return Wins(black) || Wins(white);
  }

  bool IsWin() const {
    return white_to_play ? !Wins(black) : !Wins(white);
  }

  void Debug() const {
    cout << ToString();

    // Pause me!
    getchar();
  }

  void MakeMove(uint64 move) {
    hash ^= zorbist[(white_to_play * 64) + move];
    uint64 bit = 1ULL << move;
    if (white_to_play) {
      assert(!(white & bit));
      white |= bit;
      hash ^= 0x6D2BB3DE26F1825BULL;
    } else {
      assert(!(black & bit));
      black |= bit;
    }
    white_to_play = !white_to_play;
  }

  string ToString() const {
    string str;
    for (int i = 0; i < 8; ++i) {
      for (int j = 0; j < 8; ++j) {
        if (PieceAtPosition(black, i, j)) {
          str += "x ";
        } else if (PieceAtPosition(white, i, j)) {
          str += "o ";
        } else {
          str += ". ";
        }
      }
      str += "\n";
    }
    return str;
  }

  void FromString(const char *board) {
    hash = 0xF8EC3588B56CB38AULL; // Doesn't matter because it's the root.
    black = 0;
    white = 0;
    for (int i = 0; i < 8; ++i) {
      for (int j = 0; j < 8; ++j) {
        uint64 bit = BitForPosition(i, j);
        char c = board[17 * i + 2 * j];
        if (c == 'o') {
          white |= bit;
        }
        if (c == 'x') {
          black |= bit;
        }
      }
    }
  }

  uint64 black;
  uint64 white;
  uint64 hash;
  bool white_to_play;
};

